package wtx.geek;

import java.util.*;
import java.util.Random;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.ForkJoinTask;
import java.util.concurrent.Future;

import com.google.common.base.Joiner;
import javafx.util.Pair;
import sun.plugin.dom.exception.InvalidStateException;

/**
 * given input array: [a1, a2, a3, ... an, b1, b2, b3, ..., bn]
 * exchange element in place to get
 * [a1, b1, a2, b2, ..., an, bn]
 */

public class Solution {
    final static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }
    public static ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null) {
            return null;
        }
        ListNode sentialNode = head;
        int i;
        // 注意这里是先++i, 再执行判断
        for (i = 0; i < n && sentialNode != null; ++i) {
            sentialNode = sentialNode.next;
        }
        if (sentialNode != null) {
            ListNode prevNode = head;
            sentialNode = sentialNode.next;
            while(sentialNode != null) {
                prevNode = prevNode.next;
                sentialNode = sentialNode.next;
            }
            ListNode delNode = prevNode.next;
            prevNode.next = delNode.next;
            return head;
        } else {
            if (i == n) {
                ListNode newHead = head.next;
                head.next = null;
                return newHead;
            } else {
                return head;
            }
        }

    }
    public static String printList(ListNode head) {
        StringJoiner sj = new StringJoiner(", ");
        while (head != null) {
            sj.add(String.valueOf(head.val));
            head = head.next;
        }
        return sj.toString();
    }
    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        ListNode nextNode = head.next = new ListNode(2);
        nextNode = nextNode.next = new ListNode(3);

        System.out.println(printList(head));
        head = removeNthFromEnd(head, 4);
        System.out.println(printList(head));
    }
}
